package xio.leetcode.java;

import xio.leetcode.java.base.ListNode;


/**
 * leetcode 174
 * Sort a linked list using insertion sort.
 *
 * 插入排序算法：
 *
 *  插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 *  每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 *  重复直到所有输入数据插入完为止。
 *
 * 链表的插入排序实现
 *
 * 思路：如上算法原理所说，对应在链表中，"每次移动一个元素"，我们可以new 一个 listnode (代码中对应 run)来作为这个指针；
 *      每次都比较 run 与 run.next 的值，如果 next 的值更大，那就符合预期排序了，直接移动到下一个元素，即 run = run.next;
 *      如果 next 的值小于当前节点的值，那就需要在之前已经排序好的链表中找到一个比这个 next 值（代码中对应 smaller）大的节点（对应 pre），并插入到其前面；
 *      全部移动完，即完成排序；
 *  栗子：
 *     链表：2 -> 5 -> 4 -> 1
 *     run 开始指向 2， run.next = 5; 5 > 2 继续下一个
 *     run 指向了 5 ，run.next = 4; 5 < 4, 开始找合适位置 pre 插入：
 *              pre 默认从头开始，pre = 2 < 4;继续
 *              pre = 5 > 4; 找到了合适的位置，把4插入到 5 前面：
 *                  插入前先让 run 移到下一个位置(即代码中的run.next = smaller.next;)
 *                  然后插入；
 *     省略后续类似过程...
 *
 */
public class LC174_InsertionSortList {

    public ListNode insertionSortList(ListNode head) {
        if (head==null ||head.next==null){
            return head;
        }
        ListNode start = new ListNode(Integer.MIN_VALUE);
        start.next = head;
        ListNode run = head;

        while (run.next !=null){
            if (run.val > run.next.val){
                ListNode pre = start;
                // 小的那个节点，即需要找到合适位置插入的节点
                ListNode smaller = run.next;
                while (pre.next.val < smaller.val){
                    pre = pre.next;
                }
                // 插入前逞着 smaller 还是指向下一个没有经过的节点，先把 run 移到下一个位置
                run.next = smaller.next;

                // 把 smaller 节点插入到合适的节点 pre 后面
                ListNode tmp = pre.next;
                pre.next = smaller;
                smaller.next = tmp;

            }else {
                run = run.next;
            }
        }
        return start.next;
    }
}
